class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        res = []
        queens = [0] * n # 记录每行皇后的位置
        col = [False]*n
        diag1 = [False]*(n*2-1)
        diag2 = [False]*(n*2-1)
        # 用嵌套函数写法 简单
        def dfs(r):
            if r==n:
                res.append(['.' * c + 'Q' + '.' * (n - 1 - c) for c in queens])
                return
            for c,ok in enumerate(col):
                if not ok and not diag1[r+c] and not diag2[r-c]:
                    queens[r] = c
                    col[c] = diag1[r+c] = diag2[r-c]=True
                    dfs(r+1)
                    col[c] = diag1[r+c] = diag2[r-c]= False
            
        dfs(0)
        return res 



if __name__ == "__main__":
    so = Solution()
    print(so.solveNQueens(4))